package com.xigua._搜索或回溯算法;

import com.xigua.TreeNode;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 * @date 2022/3/2012:57
 */
public class _剑指Offer54_二叉搜索树的第k大节点 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode left = new TreeNode(3,new TreeNode(2,new TreeNode(1),null),new TreeNode(4));
        TreeNode right = new TreeNode(6);
        root.left = left;
        root.right = right;
        Solution solution = new Solution();
        solution.kthLargest(root,1);
    }

}

class Solution {
    int k;
    int ans;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }

    void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.right);
        if (k == 0) return;
        if (--k == 0) ans = root.val;
        dfs(root.left);


    }
}
